package com.qz.sort;

import sun.misc.LRUCache;

import java.awt.image.AreaAveragingScaleFilter;
import java.beans.beancontext.BeanContext;

/**
 * @Description 归并排序 从小到大
 * @Author Flag
 * @Date: 2021/8/8 15:06
 * @Version: 1.0
 **/
public class MergeSortDome {
    public static void main(String[] args) {
        int[] array = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] ints = mergeSort2(array, 0, array.length - 1);

        for (int anInt : ints) {

            System.out.print(anInt+" ");
        }
    }

    public static int[] mergeSort(int[] array,int left, int right) {
        //{8,4,5,7,1,3,6,2};
        //1.首先先将归并排序的数据拆分为开
        if(left < right) {
            int mid = (left+right)/2;
            mergeSort(array, left, mid);
            mergeSort(array, mid+1, right);

            //合并时，每合并一次，就
            merge(array,left,mid,right);
        }

        return array;
    }




    /**
     * 合并的方法  从小到大
     *
     * @param array 数组
     * @param left  数组的左边指针
     * @param mid   右半部分数组第一个元素的前一个
     * @param right 右半部分数组的最后一个
     */
    public static void merge(int[] array, int left, int mid, int right) {

        //代表左侧的第一个元素
        int leftBegin = left;
        //代表右测的第一个元素
        int rightBegin = mid + 1;
        //定义一个中间量数组
        int[] temp = new int[20];
        //定义中间数组的首个坐标
        int tempIndex = 0;
        //region 自创版本一  2021年8月8日 15点29分
//        while (leftBegin == mid && rightBegin == right){
//
//            //左边没有了，就把右边全部放进去
//            if(leftBegin <= mid && rightBegin <= right){
//                //左边数组的数据小
//                if(array[leftBegin] <array[rightBegin]){
//                    //左边数据放到新数组，然后
//                    temp[tempIndex] = array[leftBegin];
//                    leftBegin ++;
//                    tempIndex++;
//                } else if (array[leftBegin]> array[rightBegin]){
//                    //右边数据放到新数组，然后
//                    temp[tempIndex] = array[rightBegin];
//                    leftBegin ++;
//                    tempIndex++;
//                }
//            } else {
//                while (leftBegin <= mid){
//                    //左边数据放到新数组，然后
//                    temp[tempIndex] = array[leftBegin];
//                    leftBegin ++;
//                    tempIndex++;
//                }
//                while (right <= mid){
//                    //左边数据放到新数组，然后
//                    temp[tempIndex] = array[right];
//                    leftBegin ++;
//                    tempIndex++;
//                }
//                break;
//            }
//        }
        //endregion

        //region 版本2
        //如果左半部分和右半部分都不是null，就进行比较
        while (leftBegin <= mid && rightBegin <= right) {
            //左边数组的数据小
            if (array[leftBegin] <= array[rightBegin]) {
                //左边数据放到新数组，然后
                temp[tempIndex] = array[leftBegin];
                leftBegin++;
                tempIndex++;
            } else if (array[leftBegin] > array[rightBegin]) {
                //右边数据放到新数组，然后
                temp[tempIndex] = array[rightBegin];
                rightBegin++;
                tempIndex++;
            }
        }
        //走到这里，证明已经有一部分为null
        //如果左半部分还有内容，就全部放进去
        while (leftBegin <= mid) {
            //左边数据放到新数组，然后
            temp[tempIndex] = array[leftBegin];
            leftBegin++;
            tempIndex++;
        }
        //如果右半部分还有内容，也全部放进去
        while (rightBegin <= right) {
            //左边数据放到新数组，然后
            temp[tempIndex] = array[rightBegin];
            rightBegin++;
            tempIndex++;
        }
        //endregion
        //将中间数组的内容移动到新数组中
        tempIndex=0;
        for (int i = left; i <= right ; i++,tempIndex++) {
            array[i] = temp[tempIndex];
        }

    }


    /**
     * 归并排序，从小到大  先回忆一下啊  兄弟 啥是归并排序。。归并排序是啥？ 我想起不了。 先拆在分 。 对 两个有序的数组
     * @param array
     * @param left
     * @param mid
     * @param right
     */
    public static void merge2(int[] array, int left, int mid, int right,int[] temp) {
        //左指针
        int leftBegin = left;
        //右指针
        int rightBegin = mid + 1;

        int tempIndex = 0;

        //证明两个数组都有元素
        while (leftBegin<= mid && rightBegin <= right){
            //证明左边的数组小
            if(array[leftBegin] <= array[rightBegin]){
                //放进去
                temp[tempIndex] = array[leftBegin];
                leftBegin++;
                tempIndex++;
            } else{
                temp[tempIndex] = array[rightBegin];
                rightBegin++;
                tempIndex++;
            }
        }

        while (leftBegin <= mid){
            temp[tempIndex] = array[leftBegin];
            leftBegin++;
            tempIndex++;
        }

        while (rightBegin<= mid){{
            temp[tempIndex] = array[rightBegin];
            rightBegin++;
            tempIndex++;
        }}

        //数组在复制回来
        for (int i = 0; i < tempIndex; i++) {
            array[left] = temp[i];
            left++;
        }

    }

    public static int[] mergeSort2(int[] array,int left, int right) {

        int[] temp =new int[10];
        //为什么不能用等于
        if(left < right){
            int mid = (right+left)/2;
            mergeSort2(array,left,mid);
            mergeSort2(array,mid+1,right);
            merge2(array,0,mid,right,temp);
        }


        return array;
    }


}
